Many computations performed on digital computers involve division of an integer by a power of two. For example, image compression computations utilizing the Haar transform require the computation of the sum and differences of adjacent pixel values divided by two. Similarly, multiplication by a binary fraction can be decomposed into a plurality of addition operations in which one operand is generated from the division of an integer by a power of two and the subsequent addition of the result to a second integer.
The fastest method for performing a division of an integer by 2.sup.m is to shift the integer to the right by m places. Such shifts can be carried out in a single instruction cycle. Hence, this procedure has significant advantages. Unfortunately, the result obtained by this method is always rounded downward with the bits shifted out being discarded. This will be referred to as truncation rounding in the following discussion. While such downward rounding may be acceptable in many circumstances, there are a number of cases in which it is undesirable. For example, if a sequence of computations are to be performed in which each computation depends on the result of a previous computation, the round off error will be larger if all of the computations utilized truncation rounding.
In addition, it is often important to maintain certain statistical properties when operating on a large set of values. Consider the case in which an image is to be reduced in size by averaging adjacent pixels in the image. That is, each group of 4 pixels is to be replaced by one pixel having a value equal to the average of the 4 pixels replaced. The image is represented by an I.times.I pixel array. The pixel reduction can be accomplished by averaging the odd and even rows in the array to generate an I.times.I/2 pixel array. The odd and even columns of this intermediate array are then averaged to generate the final (I/2).times.(I/2) array. If the various averaging operations always round down as with truncation rounding, the final image will have different statistical properties than the original image. For example, the reduced image will have a lower average light intensity than the original array. It is often important that this type of artifact be avoided.
Broadly, it is the object of the present invention to provide an improved method and apparatus for rounding the result of an integer division by a power of two.
It is a further object of the present invention to provide an apparatus and method for dividing an integer by a power of two without biasing the result.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.